import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：旋转链表
 * 思路：和旋转数组一样，先把整体旋转，再把前K个旋转，最后把后K个旋转，最终得到的结果就是我们想要的链表
 * 优化思路：1. 快慢指针法：快指针先走k步，慢指针和快指针再一起走，当快指针走到空了，慢指针就走到了倒数第K+1个节点
 *                      其后一个节点就是我们要找的新的头节点，把其断开，再把原来的头链接即可
 *         2. 链表成环法：先将链表成环，再让指针从头节点开始走，走【长度-k-1】步就找到新的尾节点，记录位置断开，即为新链表
 */
public class Test {

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        // 计算有效的 k 值：对于与链表长度成整数倍的「旋转」都是没有意义的（旋转前后链表不变）
        int n = 0;
        ListNode cur = head;
        while (cur != null ) {
            cur = cur.next;
            n++;
        }
        k %= n;
        if (k == 0) {
            return head;
        }

        // 使用「快慢指针」找到倒数第 k 个节点（新头结点）：slow 会停在「新头结点」的「前一位」，也就是「新尾结点」
        ListNode slow = head;
        ListNode fast = head;
        while (k-- > 0) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 保存新头结点，并将新尾结点的 next 指针置空
        ListNode nHead = slow.next;
        slow.next = null;
        // 将新链表的前半部分（原链表的后半部分）与原链表的头结点链接上
        fast.next = head;
        return nHead;
    }


    public ListNode rotateRight2(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        // 先将链表成环，并记录链表的长度
        // tmp 会记录住原链表最后一位节点
        int len = 1; // 加上尾节点
        ListNode cur = head;
        while (cur.next != null) {
            len++;
            cur = cur.next;
        }
        k %= len;
        if (k == 0) {
            return head;
        }
        // 正式成环
        cur.next = head;
        // 从原链表 head 出发，走 tot - k - 1 步，找到「新尾结点」进行断开，并将其下一个节点作为新节点返回
        k = len - k - 1;
        while (k-- > 0) {
            head = head.next;
        }
        ListNode newHead = head.next;
        head.next = null;
        return newHead;
    }


    public ListNode rotateRight1(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        // 像反转数组那样，先把节点的值全部存储起来，反转，后在用链表来存储反转后的值
        ListNode cur = head;
        ArrayList<Integer> list = new ArrayList<>();
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        // 开始反转
        int n = list.size();
        if (k >= n) {
            k %= n;
        }
        // 整体反转，前k个反转，后k个反转
        func(list, 0, n-1);
        func(list, 0, k-1);
        func(list, k, n-1);
        // 接下来就可以开始创建链表了
        ListNode newHead = new ListNode(-1);
        cur = newHead;
        for (int i = 0; i < n; i++) {
            ListNode newNode = new ListNode(list.get(i));
            cur.next = newNode;
            cur = cur.next;
        }
        return newHead.next;
    }
    // 反转数组
    public void func(ArrayList<Integer> list, int left, int right) {
        while (left < right) {
            int tmp = list.get(left);
            list.set(left, list.get(right));
            list.set(right, tmp);
            left++;
            right--;
        }
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
